package leetcode.editor.vscdev.hot100;

import leetcode.editor.utils.TreeNode;

public class lc236 {
    // 给定二叉树找最近公共祖先
}

class Solution {
    // 后序遍历
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 终止条件：如果根节点为空，或者根节点就是p或q，则返回根节点
        if (root == null || root == p || root == q) {
            // 如果是p/q 代表在向下遍历的过程中找到了该节点, 初始root满足该节点祖先条件
            return root;
        }
        // 递归在左子树中查找
        TreeNode leftNode = lowestCommonAncestor(root.left, p, q);
        // 递归在右子树中查找
        TreeNode rightNode = lowestCommonAncestor(root.right, p, q);
        // 如果左右子树都找到了，说明当前节点就是最近公共祖先
        if (leftNode != null && rightNode != null) {
            return root;
        }
        // 返回非空的那一边结果
        return leftNode == null ? rightNode : leftNode;
    }
}